用 JavaScript 实现树

发表于   |   分类于

树是一种非顺序数据结构，它用于存储需要快速查找的数据非常有用。

树是一种分层数据的抽象模型。现实中最常见的例子是家谱，或是公司的组织架构：

Markdown

树的相关术语

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点：

Markdown

  • 节点：树中的每个元素都叫做节点，节点分为内部节点和外部节点。
  • 根节点：位于树顶部的节点，它没有父节点
  • 内部节点：至少有一个子节点的节点（7、5、9、15、13、20是内部节点）
  • 外部节点：没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18、25是叶节点）

有关树的另一个术语是子树。子树由节点和它的后代构成。例如，节点13、12、14构成了上图中树的一棵子树。

节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。比如，节点3有3个祖先节点，它的深度为3。

树的高度取决于所有节点深度的最大值。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。

二叉搜索树是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。

创建二叉搜索树

1
2
3
4
5
6
7
8
9
function BinarySearchTree(){
	var Node = function(key){
		this.key = key;
		this.left = null;
		this.right =null;
	};

	var root = null;
}

下图展现了二叉搜索树数据结构的组织方式：

Markdown

声明一个Node类来表示树中的每个节点，不同于之前将节点本身称作节点或项，在这里我们称作键，键是树相关的术语中对节点的称呼。

然后，我们需要实现一些方法：

  • insert(key):向树中插入一个新的键；
  • search(key):在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false；
  • inOrderTraverse:通过中序遍历方式遍历所有节点。
  • preOrderTraverse:通过先序遍历方式遍历所有节点。
  • postOrderTraverse:通过后序遍历方式遍历所有节点。
  • min:返回树中最小的值/键。
  • max:返回树中最大的值/键。
  • remove(key):从树中移除某个键。

向树中插入一个键

下面的代码是用来向树插入一个新键的算法的第一部分：

1
2
3
4
5
6
7
8
9
this.insert = function(key){
		var newNode = new Node(key);

		if (root === null) {
			root = newNode;
		}else{
			insertNode(root, newNode);
		}
	};

以上情况还需要一个私有的辅助函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var insertNode = function(node, newNode){
		if (newNode.key < node.key) {
			if (node.left === null) {
				node.left = newNode;
			}else{
				insertNode(node.left, newNode);
			}
		}else{
			if (node.right === null) {
				node.right = newNode;
			}else{
				insertNode(node.right, newNode);
			}
		}
	};

树的遍历

遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程。访问树的所有节点有三种方式：中序、先序、后序。

中序遍历

中序遍历是一种上行访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

以下是它的实现：

1
2
3
this.inOrderTraverse = function(callback){
		inOrderTraverseNode(root, callback);
	};

inOrderTraverse方法接收一个回调函数作为参数。回调函数用来定义我们对遍历到的每个节点进行操作。由于我们在BST中最常实现的算法是递归，这里使用了一个私有的辅助函数，来接收一个节点和对应的回调函数作为参数：

1
2
3
4
5
6
7
var inOrderTraverseNode(node, callback){
		if (node !== null) {
			inOrderTraverseNode(node.left, callback);
			callback(node.key);
			inOrderTraverseNode(node.right, callback);
		}
	};

下面的图描绘了inOrderTraverse方法的访问路径：

Markdown

先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

1
2
3
this.preOrderTraverse = function(callback){
		preOrderTraverseNode(root, callback);
	};

preOrderTraverseNode方法的实现如下：

1
2
3
4
5
6
7
var preOrderTraverseNode(root, callback){
		if (node !== null) {
			callback(node.key);
			preOrderTraverseNode(node.left, callback);
			preOrderTraverseNode(node.right, callback);
		}
	};

先序遍历和中序遍历的不同点是，先序遍历会先访问节点本身，然后在访问它的左侧子节点，最后是右侧子节点，下图描绘了preOrderReverse方法的访问路径：

Markdown

后序遍历

后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占用空间的大小。

1
2
3
this.postOrderTraverse = function(callback){
		postOrderTraverseNode(root, callback);
	};

postOrderTraverseNode方法的实现如下：

1
2
3
4
5
6
7
var postOrderTraverseNode = function(node, callback){
		if (node !== null) {
			postOrderTraverseNode(node.left, callback);
			postOrderTraverseNode(node.right, callback);
			callback(node.key);
		}
	};

下面的图描绘了postOrderTraverseNode方法的访问路径：

Markdown

搜索树中的值

在树中，有三种经常执行的搜索类型：

  • 最小值；
  • 最大值；
  • 搜索特定的值。

搜索最大值和最小值

Markdown

很容易看出，这棵树中的最小值在最后一层最左侧的节点，最大值在最右端的节点。

首先，我们来看寻找树的最小键的方法：

1
2
3
this.min = function(){
		return minNode(root);
	}

min方法将暴露给用户。这个方法调用了minNode方法：

1
2
3
4
5
6
7
8
9
10
var minNode = function(Node){
		if (node) {
			while(node && node.left !== null){
				node = node.left;
			}

			return node.key;
		}
		return null;
	};

以相似的方法，可以实现max方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
this.max = function(){
		return maxNode(root);
	};

	var maxNode = function(Node){
		if (node) {
			while(node && node.right !== null){
				node = node.right;
			}

			return node.key;
		}
		return null;
	};

搜索一个特定的值

实现函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
this.search = function(key){
		return searchNode(root, key);
	};

	var searchNode = function(node, key){
		if (node === null) {
			return false;
		}

		if (key < node.key) {
			return searchNode(node.left, key);
		}else if (key>node.key) {
			return searchNode(node.right, key);
		}else{
			return true;
		}
	};

移除一个节点

BST的最后一个方法，也是最难复杂的方法，就是remove，我们先创建这个方法，使它能够在树的实例上被调用：

1
2
3
this.remove = function(key){
		root = removeNode(root, key);
	};

removeNode方法的复杂之处在于我们要处理不同的运行场景，当然也包括它同样是通过递归来实现的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var removeNode = function(node, key){
		if (node === null) {
			return null;
		}
		if (key < node.key) {
			node.left = removeNode(node.left, key);
			return node;
		}else if(key>node.key){
			node.right = removeNode(node.right, key);
			return node;
		} else{
			//第一种情况——一个叶节点
			if (node.left === null && node.right ===null) {
				node = null;
				return node;
			}

			//第二种情况——一个只有一个子节点的节点
			if (node.left === null) {
				node = node.right;
				return	node;
			}else if (node.right === null) {
				node = node.left;
				return node;
			}

			//第三种情况——一个有两个子节点的节点
			var aux = findMinNode(node.right);
			node.key = aux.key;
			node.right = removeNode(node.right, aux.key);
			return node;
		}
	};
	
	var findMinNode = function(node){
        while (node && node.left !== null) {
            node = node.left;
        }

        return node;
    };

我们来分析一下第三种情况，也是最复杂的情况，那就是要移除的节点有两个子节点——左侧子节点和右侧子节点，需要执行四个步骤：

  1. 当找到了需要移除的节点后，需要找到它右边子树中最小的节点（它的继承者）。
  2. 然后，用它右侧子树中最小节点的键去更新这个节点的值。通过这一步，我们改变了这个节点的键，也就是说它被移除了。
  3. 但是，这样在树中就有两个拥有相同键的节点了，这是不行的。要继续把右侧子树中的最小节点移除，毕竟它已经被移至要移除的节点的位置了。
  4. 最后，向它的父节点返回更新后节点的引用。

下图展示了这个过程：

Markdown

下面是完整的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
function BinarySearchTree() {

    var Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    };

    var root = null;

    this.insert = function(key){

        var newNode = new Node(key);

        //special case - first element
        if (root === null){
            root = newNode;
        } else {
            insertNode(root,newNode);
        }
    };

    var insertNode = function(node, newNode){
        if (newNode.key < node.key){
            if (node.left === null){
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null){
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    };

    this.getRoot = function(){
        return root;
    };

    this.search = function(key){

        return searchNode(root, key);
    };

    var searchNode = function(node, key){

        if (node === null){
            return false;
        }

        if (key < node.key){
            return searchNode(node.left, key);

        } else if (key > node.key){
            return searchNode(node.right, key);

        } else { //element is equal to node.item
            return true;
        }
    };

    this.inOrderTraverse = function(callback){
        inOrderTraverseNode(root, callback);
    };

    var inOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    };

    this.preOrderTraverse = function(callback){
        preOrderTraverseNode(root, callback);
    };

    var preOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
        }
    };

    this.postOrderTraverse = function(callback){
        postOrderTraverseNode(root, callback);
    };

    var postOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    };

    this.min = function() {
        return minNode(root);
    };

    var minNode = function (node) {
        if (node){
            while (node && node.left !== null) {
                node = node.left;
            }

            return node.key;
        }
        return null;
    };

    this.max = function() {
        return maxNode(root);
    };

    var maxNode = function (node) {
        if (node){
            while (node && node.right !== null) {
                node = node.right;
            }

            return node.key;
        }
        return null;
    };

    this.remove = function(element){
        root = removeNode(root, element);
    };

    var findMinNode = function(node){
        while (node && node.left !== null) {
            node = node.left;
        }

        return node;
    };

    var removeNode = function(node, element){

        if (node === null){
            return null;
        }

        if (element < node.key){
            node.left = removeNode(node.left, element);
            return node;

        } else if (element > node.key){
            node.right = removeNode(node.right, element);
            return node;

        } else { //element is equal to node.item

            //handle 3 special conditions
            //1 - a leaf node
            //2 - a node with only 1 child
            //3 - a node with 2 children

            //case 1
            if (node.left === null && node.right === null){
                node = null;
                return node;
            }

            //case 2
            if (node.left === null){
                node = node.right;
                return node;

            } else if (node.right === null){
                node = node.left;
                return node;
            }

            //case 3
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
        }
    };
}